import java.util.*;

public class FSM {
    private List<FSMNode> nodes; // 所有状态节点
    private FSMNode startNode; // 起始节点
    private Set<Set<Character>> alphabet; // 字母表

    // 构造函数
    public FSM(Set<Set<Character>> alphabet) {
        this.nodes = new ArrayList<>();
        this.alphabet = alphabet;
    }

    public FSMNode getStartNode() {
        return startNode;
    }

    public void setStartNode(FSMNode startNode) {
        this.startNode = startNode;
    }

    public FSMNode getNode(int id) {
        return nodes.get(id);
    }

    public FSMNode addNode(TokenCode state, boolean isEndState) {
        FSMNode newNode = new FSMNode(nodes.size(), state, isEndState);
        nodes.add(newNode);
        return newNode;
    }

    public void addTrans(int fromId, int toId, Set<Character> input) {
        FSMNode fromNode = getNode(fromId);
        FSMNode toNode = getNode(toId);
        fromNode.addTransition(input, toNode);
    }

    public static FSM createNFA() {
        // 定义字符集合
        Set<Set<Character>> charList = new HashSet<>();
        Set<Character> letterList = AlphabetUtil.getLetters();
        charList.add(letterList);

        Set<Character> numList = AlphabetUtil.getDigits();
        charList.add(numList);

        Set<Character> zeroList = new HashSet<>();
        zeroList.add('0');
        charList.add(zeroList);

        Set<Character> dotList = new HashSet<>();
        dotList.add('.');
        charList.add(dotList);

        FSM NFA = new FSM(charList);

        // 添加状态
        FSMNode node0=NFA.addNode(TokenCode.UNDEFINED, false);
        FSMNode node1=NFA.addNode(TokenCode.INT, true);
        FSMNode node2=NFA.addNode(TokenCode.UNDEFINED, false);
        FSMNode node3=NFA.addNode(TokenCode.INT, true);
        FSMNode node4=NFA.addNode(TokenCode.IDN, true);
        FSMNode node5=NFA.addNode(TokenCode.UNDEFINED, false);
        FSMNode node6=NFA.addNode(TokenCode.IDN, true);
        FSMNode node7=NFA.addNode(TokenCode.UNDEFINED, false);
        FSMNode node8=NFA.addNode(TokenCode.FLOAT, true);
        NFA.setStartNode(node0);

        // 添加转换
        NFA.addTrans(node0.getId(), node1.getId(), zeroList);
        NFA.addTrans(node0.getId(), node1.getId(), numList);
        NFA.addTrans(node0.getId(), node2.getId(), numList);
        NFA.addTrans(node2.getId(), node2.getId(), zeroList);
        NFA.addTrans(node2.getId(), node2.getId(), numList);
        NFA.addTrans(node2.getId(), node3.getId(), zeroList);
        NFA.addTrans(node2.getId(), node3.getId(), numList);
        NFA.addTrans(node2.getId(), node7.getId(), dotList);
        NFA.addTrans(node1.getId(), node7.getId(), dotList);
        NFA.addTrans(node7.getId(), node7.getId(), zeroList);
        NFA.addTrans(node7.getId(), node7.getId(), numList);
        NFA.addTrans(node7.getId(), node8.getId(), zeroList);
        NFA.addTrans(node7.getId(), node8.getId(), numList);
        NFA.addTrans(node0.getId(), node4.getId(), letterList);
        NFA.addTrans(node0.getId(), node5.getId(), letterList);
        NFA.addTrans(node5.getId(), node5.getId(), letterList);
        NFA.addTrans(node5.getId(), node5.getId(), zeroList);
        NFA.addTrans(node5.getId(), node5.getId(), numList);
        NFA.addTrans(node5.getId(), node6.getId(), zeroList);
        NFA.addTrans(node5.getId(), node6.getId(), numList);
        NFA.addTrans(node5.getId(), node6.getId(), letterList);

        return NFA;
    }

    // NFA 转 DFA
    public FSM convertToDFA() {
        Map<Set<Integer>, FSMNode> dfaStateMap = new HashMap<>();
        Queue<Set<Integer>> stateQueue = new LinkedList<>();
        FSM DFA = new FSM(this.alphabet);

        // 初始状态
        Set<Integer> startSet = new HashSet<>();
        startSet.add(this.startNode.getId());
        FSMNode startNode = DFA.addNode(TokenCode.UNDEFINED, false);
        dfaStateMap.put(startSet, startNode);
        DFA.setStartNode(startNode);
        stateQueue.add(startSet);

        while (!stateQueue.isEmpty()) {
            Set<Integer> currentSet = stateQueue.poll();
            FSMNode currentNode = dfaStateMap.get(currentSet);

            for (Set<Character> charSet : this.alphabet) {
                Set<Integer> nextSet = new HashSet<>();
                for (int nfaState : currentSet) {
                    FSMNode nfaNode = this.getNode(nfaState);
                    Map<Set<Character>, ArrayList<FSMNode>> transitions = nfaNode.getTrans();
                    for (Map.Entry<Set<Character>, ArrayList<FSMNode>> entry : transitions.entrySet()) {
                        if (!Collections.disjoint(entry.getKey(), charSet)) {
                            for (FSMNode targetNode : entry.getValue()) {
                                nextSet.add(targetNode.getId());
                            }
                        }
                    }
                }

                if (!nextSet.isEmpty()) {
                    FSMNode nextNode = dfaStateMap.get(nextSet);
                    if (nextNode == null) {
                        boolean isEndState = false;
                        TokenCode state = TokenCode.UNDEFINED;

                        for (int nfaState : nextSet) {
                            FSMNode nfaNode = this.getNode(nfaState);
                            if (nfaNode.isEndState()) {
                                isEndState = true;
                                state = nfaNode.getState();
                            }
                        }

                        nextNode = DFA.addNode(state, isEndState);
                        dfaStateMap.put(nextSet, nextNode);
                        stateQueue.add(nextSet);
                    }

                    DFA.addTrans(currentNode.getId(), nextNode.getId(), charSet);
                }
            }
        }
        return DFA;
    }

    private FSMNode getTransitionTarget(FSMNode node, Set<Character> input) {
        for (Map.Entry<Set<Character>, ArrayList<FSMNode>> entry : node.getTrans().entrySet()) {
            if (!Collections.disjoint(entry.getKey(), input)) {
                return entry.getValue().getFirst(); // 假定 DFA 没有多重目标
            }
        }
        return null;
    }

    private int getPartitionIndex(List<Set<FSMNode>> partitions, FSMNode node) {
        for (int i = 0; i < partitions.size(); i++) {
            if (partitions.get(i).contains(node)) {
                return i;
            }
        }
        return -1; // 如果节点不属于任何分区
    }

    private Set<FSMNode> getPartitionContaining(List<Set<FSMNode>> partitions, FSMNode node) {
        for (Set<FSMNode> group : partitions) {
            if (group.contains(node)) {
                return group;
            }
        }
        return null; // 如果没有找到分区
    }


    public FSM minimizeDFA() {
        if (this.startNode == null) {
            throw new IllegalStateException("DFA must have a start node to be minimized.");
        }

        // Step 1: Partition the states into two groups: accepting and non-accepting
        Set<FSMNode> acceptingStates = new HashSet<>();
        Set<FSMNode> nonAcceptingStates = new HashSet<>();

        for (FSMNode node : this.nodes) {
            if (node.isEndState()) {
                acceptingStates.add(node);
            } else {
                nonAcceptingStates.add(node);
            }
        }

        // Initial partition
        List<Set<FSMNode>> partitions = new ArrayList<>();
        if (!acceptingStates.isEmpty()) partitions.add(acceptingStates);
        if (!nonAcceptingStates.isEmpty()) partitions.add(nonAcceptingStates);

        // Step 2: Refinement
        boolean changed;
        do {
            changed = false;
            List<Set<FSMNode>> newPartitions = new ArrayList<>();

            for (Set<FSMNode> group : partitions) {
                Map<Map<Set<Character>, Integer>, Set<FSMNode>> distinguishMap = new HashMap<>();

                for (FSMNode node : group) {
                    Map<Set<Character>, Integer> transitions = new HashMap<>();

                    for (Set<Character> input : this.alphabet) {
                        FSMNode target = getTransitionTarget(node, input);
                        int partitionIndex = getPartitionIndex(partitions, target);
                        transitions.put(input, partitionIndex);
                    }

                    distinguishMap.computeIfAbsent(transitions, k -> new HashSet<>()).add(node);
                }

                if (distinguishMap.size() > 1) {
                    changed = true;
                    newPartitions.addAll(distinguishMap.values());
                } else {
                    newPartitions.add(group);
                }
            }
            partitions = newPartitions;
        } while (changed);

        // Step 3: Create the minimized DFA
        FSM minimizedDFA = new FSM(this.alphabet);

        // Create nodes for each partition
        Map<Set<FSMNode>, FSMNode> partitionToNode = new HashMap<>();
        for (Set<FSMNode> group : partitions) {
            FSMNode representative = group.iterator().next();
            FSMNode newNode = minimizedDFA.addNode(representative.getState(), representative.isEndState());
            partitionToNode.put(group, newNode);
        }

        // Create transitions for minimized DFA
        for (Set<FSMNode> group : partitions) {
            FSMNode representative = group.iterator().next();
            FSMNode newNode = partitionToNode.get(group);

            for (Set<Character> input : this.alphabet) {
                FSMNode target = getTransitionTarget(representative, input);
                if (target != null) {
                    FSMNode targetNode = partitionToNode.get(getPartitionContaining(partitions, target));
                    minimizedDFA.addTrans(newNode.getId(), targetNode.getId(), input);
                }
            }
        }

        // Set the start node for the minimized DFA
        minimizedDFA.setStartNode(partitionToNode.get(getPartitionContaining(partitions, this.startNode)));

        return minimizedDFA;
    }


    public TokenCode getTokenCode(String token) {
        if (token == null || token.isEmpty()) {
            return TokenCode.UNDEFINED; // 空字符串或 null 返回 UNDEFINED
        }

        FSMNode node = getStartNode();
        if (node == null) {
            throw new IllegalStateException("Start node is not set in the FSM.");
        }

        for (int index = 0; index < token.length(); index++) {
            char c = token.charAt(index);
            // 获取字符对应的字母集合
            Set<Character> letterSet = Util.getLetterList(c);

            // 检查是否存在对应的转移
            if (node.getTrans().containsKey(letterSet)) {
                node = node.getTrans().get(letterSet).getFirst(); // 获取转移后的第一个节点
            } else {
                return TokenCode.UNDEFINED; // 转移失败直接返回 UNDEFINED
            }
        }

        // 检查最终状态是否为接受状态
        return node.isEndState() ? node.getState() : TokenCode.UNDEFINED;
    }


}
